package org.aplombh.java.interview.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class _204_计数质数 {
    public static void main(String[] args) {
        System.out.println(new _204_计数质数().countPrimes(499979));
    }

    private static final int[] all = new int[5000000 + 1];

    static {
        Arrays.fill(all, -1);
    }

    public int countPrimes(int n) {
        int sum = 0;
        for (int i = 2; i < n; i++) {
            if (isPrimes(i) == 1)
                sum++;
        }
        return sum;
    }

    public static int isPrimes(int n) {
        if (all[n] == -1) {
            for (int i = 2; i <= n / 2; i++) {
                if (n % i == 0) {
                    all[n] = 0;
                    return 0;
                }
            }
            all[n] = 1;
        }
        return all[n];
    }
}

class _204_计数质数_2 {
    public int countPrimes(int n) {
        boolean[] isPrim = new boolean[n];
        Arrays.fill(isPrim, true);

        for (int i = 2; i * i < n; i++) {
            if (isPrim[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrim[j] = false;
                }
            }
        }
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (isPrim[i]) {
                cnt++;
            }
        }
        return cnt;
    }
}
